#pragma once
#include<iostream>
#include<vector>

using namespace std;


template<class K>
class HashFunc {
public:
	size_t operator()(const K& key) {
		return (size_t)(key);
	}
};

template<>
class HashFunc<string> {
public:
	size_t operator()(const string& str) {
		size_t sum = 0;
		for (auto e : str) {
			sum *= 131;
			sum += e;
		}
		return sum;
	}
};

template<class T>
class HashData {
public:
	T _data;
	HashData<T>* _next;

public:
	HashData(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};

template<class K, class T, class KeyOfT, class Func >
class HashTable;

template<class K,class T,class Ptr,class Ref,class KeyOfT,class Func=HashFunc<K>>
class HashIterator {
public:
	typedef HashData<T> Node;
	typedef HashIterator<K, T,Ptr,Ref, KeyOfT, Func> Self;
	typedef HashIterator<K, T, T*, T&, KeyOfT, Func> iterator;
	typedef HashIterator<K, T, const T*, const T&, KeyOfT, Func> const_iterator;
	HashTable<K, T, KeyOfT, Func>* _pht;
	Node* _node=nullptr;
public:
	HashIterator(Node* node, HashTable<K, T, KeyOfT, Func>* pht)
		:_node(node)
		,_pht(pht)
	{}

	HashIterator(const iterator& it)
		:_node(it._node)
		,_pht(it._pht)
	{}

	Self& operator++() {
		if (_node->_next) {
			_node = _node->_next;
		}
		else {
			KeyOfT kot;
			Func fun;
			size_t hashi = fun(kot(_node->_data)) % _pht->_table.size();
			size_t i;
			for ( i= hashi+1; i < _pht->_table.size(); ++i) {
				if (_pht->_table[i]) {
					_node =_pht-> _table[i];
					break;
				}
			}
			if (i == _pht->_table.size())
				_node = nullptr;
		}
		return *this;
	}

	T& operator*() {
		return _node->_data;
	}

	T* operator->() {
		return &_node->_data;
	}

	bool operator!=(const Self& self) {
		return _node != self._node;
	}

	bool operator==(const Self& self) {
		return _node == self._node;
	}

};



template<class K,class T,class KeyOfT,class Func=HashFunc<K>>
class HashTable {
public:
	vector<HashData<T>*> _table;
	size_t _n = 0;

public:
	typedef HashData<T> Node;
	typedef typename HashIterator< K,   T,T*,T& ,  KeyOfT, Func >::iterator iterator;
	typedef typename HashIterator<K, T, const T*, const T&, KeyOfT, Func>::const_iterator const_iterator;
	template<class K, class T,class Ptr,class Ref, class KeyOfT, class Func >
	friend class HashIterator;
public:
	HashTable() {
		_table.resize(10,nullptr);
	}

	~HashTable(){
		for (size_t hashi = 0; hashi < _table.size(); ++hashi) {
			if (_table[hashi]) {
				Node* cur = _table[hashi];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
			_table[hashi] = nullptr;
		}
		_n = 0;
	}

	iterator begin() {
		size_t hashi = 0;
		while (hashi < _table.size()) {
			if (_table[hashi])
				return iterator(_table[hashi], this);
			++hashi;
		}
		return iterator(nullptr, this);
	}

	const_iterator begin()const {
		size_t hashi = 0;
		while (hashi < _table.size()) {
			if (_table[hashi])
				return const_iterator(_table[hashi], this);
			++hashi;
		}
		return const_iterator(nullptr, this);
	}

	iterator end() {
		return iterator(nullptr, this);
	}

	const_iterator end()const {
			return const_iterator(nullptr, this);
	}

	pair<iterator,bool> Insert(const T& data) {
		KeyOfT kot;
		Func func;
		iterator it = Find(kot(data));
		if (it!=end()) {
			return make_pair(it,false);
		}
		if (_n == _table.size()) {
			//HashTable<K, T, KeyOfT, Func> NewHT;
			vector<HashData<T>*> new_table;
			new_table.resize(2 * _n,nullptr);
			for (size_t i = 0; i < _n; ++i) {
				Node* cur = _table[i];
				while (cur) {
					Node* next = cur->_next;
					size_t newhashi = func(kot(cur->_data))%(new_table.size());
					cur->_next = new_table[newhashi];
					new_table[newhashi] = cur;
					cur = next;
				}
			}
			_table.swap(new_table);
		}
		size_t hashi = func(kot(data)) % _table.size();
		 Node* newnode = new HashData<T>(data);
		//head insesrt
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++_n;
		return make_pair(iterator(newnode,this), true);
	}

	iterator Find(const K& key) {
		Func func;
		KeyOfT kot;
		size_t hashi = func(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur) {
			if (kot(cur->_data) == key) {
				return iterator(cur,this);
			}
			cur = cur->_next;
		}
		return iterator(nullptr,this);
	}

	bool Erase(const T& data) {
		KeyOfT kot;
		Node* result = Find(kot(data));
		if (result) {
			size_t hashi = func(kot(data)) % _table.size();
			Node* cur = _table[hashi];
			if (cur->_data == data) {
				_table[hashi] = nullptr;
			}
			else {
				Node* pre = nullptr;
				while (cur) {
					if (cur->_data == data) {
						pre->next = cur->next;
						break;
					}
					pre = cur;
					cur = cur->next;
				}
			}
			delete cur;
			--_n;
			return true;
		}

		return false;
	}

	 
};